package main

import (
	. "local/algorithm/util"
)

/**
https://www.youtube.com/watch?v=YZ7Lm8AKwPs
Right作为后继指针
Left作为前驱指针
1.中序遍历BST，构建有序双向链表
2.双向链表头尾相连，返回头结点

*/
func main() {
	t := generateBst()
	list := bstToLinkedList(t)
	PrintBst(list)
}

var prev *TreeNode

func bstToLinkedList(root *TreeNode) *TreeNode {
	//corner case
	if root == nil {
		return root
	}

	dn := &TreeNode{}
	prev = dn
	var helper func(root *TreeNode)
	helper = func(root *TreeNode) {
		//递归跳出条件
		if root == nil {
			return
		}
		//中序遍历，串联节点
		helper(root.Left)
		prev.Right = root //Right连接下一个节点
		root.Left = prev  //Left连接上一个节点
		prev = root
		helper(root.Right)
	}

	//连接各个节点
	helper(root)
	//首尾相连
	prev.Right = dn.Right
	dn.Right.Left = prev
	return dn.Right
}

func generateBst() *TreeNode {
	//[5,3,6,2,4,null,7]
	root := &TreeNode{Val: 5}
	root.Left = &TreeNode{Val: 3}
	root.Right = &TreeNode{Val: 6}
	root.Left.Left = &TreeNode{Val: 2}
	root.Left.Right = &TreeNode{Val: 4}
	return root
}
